package day_2022_9_to_12.Day;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author haomin
 * @date 2022/10/25 15:22
 **/
public class Day53_1_Num934_ShortestBridge {
    class Solution {
        int[] dx = {-1, 0, 1, 0}, dy = {0, -1, 0, 1};
        public int shortestBridge(int[][] grid) {
            int n = grid.length;
            Deque<int[]> q = new LinkedList<>();
            boolean f = true; // 标记是否找到第一个岛屿
            for(int i = 0; i < n && f; ++i){
                for(int j = 0; j < n && f; ++j){
                    if(grid[i][j] == 1) {
                        dfs(grid, i, j, n, q);
                        f = false;
                    }
                }
            }
            int step = 0;
            while(!q.isEmpty()){
                int size = q.size();
                for(int k = 0; k < size; ++k){
                    int[] cur = q.poll();
                    for(int d = 0; d < 4; ++d){
                        int x = cur[0] + dx[d], y = cur[1] + dy[d];
                        if(x >= 0 && x < n && y >= 0 && y < n){
                            if(grid[x][y] == 0){
                                q.offer(new int[]{x, y});
                                grid[x][y] = -1;
                            }else if(grid[x][y] == 1) return step;
                        }
                    }
                }
                step++;
            }
            return 0;
        }
        private void dfs(int[][] grid, int i, int j, int n, Deque<int []> q){
            q.offer(new int[]{i, j});
            grid[i][j] = -1;
            for(int k = 0; k < 4; ++k){
                int x = i + dx[k], y = j + dy[k];
                if(x >= 0 && x < n && y >= 0 && y < n && grid[x][y] == 1)
                    dfs(grid, x, y, n, q);
            }
        }
    }
}